1. Field of the Invention
The present invention relates to a search engine or a search method.
2. Description of the Related Art
Conventionally, to attain a high-speed search, the use of a CAM (Content Addressable Memory) is known. For example, in a router or the like, the CAM is used for increasing the speed of an IP address search in a TCP/IP process. In search processing including range designation, it is impossible to use the conventional CAM and software is used to execute sequential comparison/search processing. For example, an SPD (Security Policy Database) used in IPsec (IP Security Protocol) is searched by a plurality of elements and search conditions different for respective elements, and the search conditions include range designation. The SPD serves as a database for managing security policies, and IPsec processes packets in accordance with the security policies.
Such search processing is also done in a filtering process for combating, for example, DoS (Denial of Service) attack. The search processing is executed in not only network protocol processing but also image processing.
In a device having a high-speed CPU such as a PC (Personal Computer), performing such search processing does not degrade performance significantly. If, however, a product incorporates a CPU, such as that included in an inexpensive consumer device, which has a performance lower than the CPU of a PC, and the CPU is responsible for implementing the main functions of the product, it is difficult for the CPU to execute search processing which generally imposes a heavy load. There has also been proposed a technique which extends the conventional CAM using a magnitude comparator to be able to perform a comparison of magnitudes, as disclosed in U.S. Pat. No. 7,230,839.
According to the proposal disclosed in U.S. Pat. No. 7,230,839, it is impossible to recombine search elements unlike the above-described search processing. Furthermore, in this proposal, it is impossible to recombine search conditions (match, mismatch, range, out-of-range) or to simultaneously search for a plurality of combinations of elements.
The magnitude comparator disclosed in U.S. Pat. No. 7,230,839 is formed by special cells, and is unsuitable for developing an LSI to be mounted on an inexpensive consumer device in terms of selection of a semiconductor development vendor, a development period, and cost. There is a demand for a search engine which can be formed by standard logic cells that have been widely used.
The present invention makes it possible to execute various search processes with a single search engine. Other features of the present invention will become apparent from the following description of exemplary embodiments.